7714. Фрезерные станки

Fab лаборатория – это открытая небольшая мастерская, где можно создать или изготовить практически все, что захотите, в основном с помощью инструментов с компьютерным управлением, таких как лазерный резак или 3D-принтер. Недавно фабрика FAU получила фрезерный станок с ЧПУ. Используя фрезерный станок, Вы можете резать или удалять материал с поверхности заготовки разными инструментами. Он управляется компьютерной программой.

Иногда мне было интересно, что произойдет, если несколько заготовок разной формы будут отправлены через одну программу фрезерования. Для упрощения предположим, что у нас есть только двумерные заготовки без отверстий. Программа фрезерования состоит из нескольких шагов. Каждый шаг описывает, где фрезерный станок должен удалить материал (с помощью различных инструментов) с верхней части поверхности.

Вход. Первая строка состоит из двух целых чисел w и s (1 ≤ w, s ≤ 10⁴), где w количество деталей, а s количество шагов в программе фрезерования. Следующая строка состоит из двух целых чисел x и y (1 ≤ x, y ≤ 100), где x – ширина, а y – максимально возможная высота заготовки.

Каждая из следующих w строк описывает одну деталь. Описание каждой детали состоит из x целых неотрицательных чисел, определяющих высоту поверхности в этом столбце.

Каждая из следующих s строк описывает один шаг фрезерования в программе. Описание каждого шага фрезерования состоит из x целых неотрицательных чисел s_i (0 ≤ s_i ≤ y), определяющих количество отрезанной поверхности. каждый столбец (относительно высоты области фрезерования, т.е. y, а не относительно верха заготовки). Смотрите рисунок.

Выход. Для каждой заготовки выведите одну строку, содержащую x целых чисел, определяющих оставшуюся высоту поверхности (в том же порядке, как и во входных данных).

Рисунок. Вторая деталь в первом примере: исходная деталь с последующим фрезерованием в каждом столбце – значение в программе фрезерования определяет вертикальное положение фрезерной головки.

Пример входа 1	Пример выхода 1
2 1 3 4 4 4 4 4 2 3 2 3 0	2 1 4 2 1 3
Пример входа 2	Пример выхода 2
1 3 10 100 11 22 33 44 55 66 77 88 99 100 1 100 1 100 1 100 1 100 1 100 58 58 58 58 58 58 58 58 58 58 42 42 42 42 42 42 42 42 66 42	11 0 33 0 42 0 42 0 34 0

РЕШЕНИЕ

математика

Анализ алгоритма

Программа фрезерования состоит из s шагов. Пусть на i-ом (1 ≤ i ≤ s) шаге фрезерования от поверхности в столбце j (1 ≤ j ≤ x) будет отрезано m_ij. Тогда очевидно, что суммарно в столбце j будет отрезано max(m_1j, m_2j, …, m_sj). Схемой фрезерования будем называть набор целых чисел (cuts₁, cuts₂, …, cuts_x), где

cuts_j = max(m_1j, m_2j, …, m_sj), 1 ≤ j ≤ x

Одна и та же схема фрезерования применяется ко всем w деталям. Вычислив значения cuts_j (1 ≤ j ≤ x), применим схему фрезерования к каждой детали.

Реализация алгоритма

Объявим рабочие массивы. Информация о деталях будет храниться в массиве detail. Схему фрезерования будем хранить в массиве cuts.

int detail[10001][101], cuts[101];

Читаем входные данные.

scanf("%d %d %d %d", &w, &s, &x, &y);

Читаем информацию о w деталях.

for (i = 0; i < w; i++)

for (j = 0; j < x; j++)

scanf("%d", &detail[i][j]);

Читаем и обрабатываем s шагов в программе фрезерования. cuts[j] будет содержать самый глубокий вырез в позиции j.

for (i = 0; i < s; i++)

for (j = 0; j < x; j++)

{

scanf("%d", &val);

if (val > cuts[j]) cuts[j] = val;

}

Максимально возможная высота заготовки равна y. Фрезерная головка в позиции j опускается на глубину cuts[j]. Следовательно в позиции j от i-ой детали останется высота, равная min(detail[i][j], y – cuts[j]).

for (i = 0; i < w; i++)

{

for (j = 0; j < x; j++)

printf("%d ", min(detail[i][j], y - cuts[j]));

printf("\n");

}